#include <iostream>

#include <random>
#include <ctime>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct BSTNode 
{
	int data;
	BSTNode* left;
	BSTNode* right;
};

void addBSTNode(BSTNode* parent, BSTNode* node)
{
	if (parent == NULL)
	{
		parent = node;
		return;
	}
	
	BSTNode* root = parent;

	if (node->data > root->data) 
	{
		if (nullptr == root->right)
		{
			root->right = node;
			return;
		}
	}
	else
	{
		if (nullptr == root->left)
		{
			root->left = node;
			return;
		}
	}

	for(;;)
	{
		if (node->data > root->data)
		{
			if (nullptr != root->right)
			{
				root = root->right;
			}
			else
			{
				root->right = node;
				break;
			}
		}
		else
		{
			if (nullptr != root->left)
			{
				root = root->left;
			}
			else
			{
				root->left = node;
				break;
			}
		}
	}
}

BSTNode* findInBST(int ele, BSTNode* parent)
{
	if (nullptr == parent)
	{
		return NULL;
	}

	BSTNode* root = parent;

	for(;;)
	{
		if (nullptr == root->left && nullptr == root->right)
		{
			break;
		}

		if (ele == root->data)
		{
			return root;
		}
		else if (ele > root->data)
		{
			root = root->right;
		}
		else if (ele < root->data)
		{
			root = root->left;
		}
	}
}


int main()
{
	BSTNode* roots = (struct BSTNode*)malloc(sizeof(struct BSTNode));
	roots->left = 0;
	roots->right = 0;

	srand(2200);
	for (int i = 0; i < 10; i++)
	{
		int curr = rand();
		if (i == 0)
		{
			roots->data = curr;
		}
		else
		{
			BSTNode* bstn =(struct BSTNode*)malloc(sizeof(struct BSTNode));
			bstn->data = curr;
			bstn->left = NULL;
			bstn->right = NULL;
			addBSTNode(roots, bstn);
		}
	}
	cout << "Done" << endl;

	BSTNode* result = findInBST(21407, roots);
	cout << result->data << endl;
	return 0;
}